Imaging technologies which employ raster and/or matrix addressing techniques are used widely in electronic printing and in electronic display devices. These technologies create two-dimensional images from small image dots, or picture elements (pixels), placed in a two-dimensional, addressable array. The size and spatial placement frequency of these pixels are important variables defining the quality of the images which can be produced by raster and matrix imaging systems. FIG. 1 depicts an alphanumeric character produced by a prior art raster imaging system. A raster imaging system produces output by scanning successive lines of dots onto a surface. Laser xerographic, inkjet, electrostatic, thermal transfer, magnetographic, dot matrix, ion deposition, laser film and laser erosion are all raster imaging systems.
The picture elements in a printed image are typically arranged in such fashion that a simulation, or analog, of the ideal printed image is provided. The degree to which this analog simulates the ideal or "perfect" rendering of the image is dependent upon a number of factors in the imaging system including spatial addressability, pixel size, dynamic density range of pixels (number of gray levels), placement consistency, rasterizing algorithms and consistency of the imaging process. To the extent that each of these variables is not optimized, the overall quality of the printed or displayed image may be compromised.
Most raster image printing systems in use today employ simple rendering techniques that approximate the ideal image by constructing an array of high contrast pixels. An example of an alphanumeric character produced by such an array is depicted in FIG. 1. The black areas are the imaged pixels. The small overlapping circles depict the addressable locations where pixels can be placed.
While current raster and matrix based imaging systems produce reasonable simulations of ideal images, they can also produce a variety of undesirable artifacts. These artifacts include jaggies, raster pitch errors, quantization errors and grainy halftone images. All of these terms relate to defects which are caused by the fact that the images are created by approximating the optimum rendering of the image, subject to limitations in the spatial addressability of the two-dimensional matrix array. The precision with which image pixels are placed in the array is referred to as addressability. The addressability of typical current generation laser printers is 300 dots/inch. This means that the smallest incremental distance in which a pixel can be positioned in a 300 dot/inch laser printer is 1/300 inch.
Some of the above artifacts result from periodically occurring errors in the spatial placement of some of the image pixels. These pixel placement errors result in a structured pattern in the image which is frequently noticeable to the human eye, and which can be quite objectionable. An example of such an artifact is the jagged appearance of the edge of a straight line, such as the edge of the letter A in FIG. 1, which is rendered at an angle diagonal to the primary axes of a two-dimensional matrix array.
When viewing a document or a display, an observer sees an image comprised of a large number of image features. The degree to which the observer can detect various features in the image depends upon a variety of factors, one of which is the size of the feature of interest. The degree to which features of varying size can be detected by the observer is dependent upon the visual system spatial frequency response of the observer. FIG. 16 depicts the spatial frequency response of a typical observer viewing a printed document. This figure shows the degree to which the observer can detect variations in optical density (i.e., density modulation) which occur periodically across a page as a function of the spatial frequency of the density modulation. A high spatial frequency corresponds to very small image elements and/or spaces between elements. A low spatial frequency corresponds to large image elements and/or spaces between elements. It will be noted that the peak visual response to spatially modulated density patterns occurs at spatial frequencies of about 0.5-2 cycles/mm.
One type of undesirable artifact is called a "jaggie". FIG. 2 is a magnified view of the letter "A" produced on a matrix imaging device which exhibits a jagged edge, or jaggie. It will be noted that the quantization errors associated with placing pixels in the available matrix locations create periodically varying pixel placement errors along the imaged line. Depending upon the magnitude of each placement error and the spatial frequency of periodically occurring errors, such a raster artifact may or may not be visible to the naked eye.
The degree to which the jaggie depicted in FIG. 2 is noticeable to the human eye depends upon the magnitude and frequency of the jaggies and their relationship to the spatial frequency response of the human observer. The detectability (and thus the objectionability) of these raster artifacts is determined by both the amplitude and the frequency of the jaggies, mapped against the human visual spatial frequency response as indicated in FIG. 3. If the combination of raggedness amplitude and spatial frequency of a jagged edge of an image falls below the detectability threshold, as indicated in FIG. 3, then the jaggie will not be detected under normal viewing conditions. If, however, the amplitude and spatial frequency of periodically occurring jaggies falls above the detectability threshold, then the jaggies will be noticeable to most observers.
This does not necessarily mean that jaggies located just above the detectability threshold will be objectionable. Objectionability of jaggies is subjective and can vary considerably from one observer to another. In general, however, the further above the detectability threshold that a given jagged image element lies, the more noticeable and the more objectionable such a jagged artifact will be to most observers.
A variety of techniques have been developed to reduce the objectionability of jaggies and other artifacts in raster and matrix imaging systems. Many prior art anti-aliasing techniques have been developed for CRT displays. These techniques reduce the appearance of jaggedness in lines oriented off the horizontal or vertical axes by blurring or smoothing the image elements at transition steps or inflection points. This blurring is depicted graphically in FIG. 4. Such intentional blurring is accomplished by gradually varying the intensity of the CRT electron beam as it approaches the jagged image transitions. In non-antialiased CRT displays, there is an abrupt intensity transition across these image edges.
A variety of prior art techniques have been developed for smoothing edge artifacts, such as jaggies, specifically in electrophotographic printing systems including laser printers. U.S. Pat. No. 4,625,222 assigned to IBM, discloses techniques in which gray pixels are substituted for black or white pixels in a laser printing system to smooth the density transition between image and background areas at jagged edges. The IBM technique substitutes these gray pixels during rasterization of the high level representation of the computer-generated image. This substitution occurs as part of the formation of the bit-mapped rendition of the image in the printer raster image processor. The substitution of gray pixels at this point in the imaging process requires the use of a multiple plane bit-map to enable the digital representation of image pixels using values other than black or white. More than one bit per pixel is required if more than two values of output density per pixel are to be rendered. The use of a multiple plane bit-map increases the amount of RAM required in the raster image processor (RIP), which increases the cost of the RIP correspondingly. Furthermore, the IBM technique modulates the laser beam intensity to enable imaging of gray pixels. This requires additional hardware which adds significantly to the cost of the system.
Other techniques have been disclosed in U.S. Pat. No. 4,437,122 assigned to Xerox and U.S. Pat. No. 4,847,641 assigned to Hewlett-Packard. These techniques are directed to enhancing the quality of raster images produced on laser printing systems. Both the Xerox and the Hewlett-Packard techniques enhance the edge characteristics of raster images.
The pattern matching process in the Xerox and Hewlett-Packard patents is performed on a pixel-by-pixel basis to identify individual pixels which are to be corrected. Corrections on these identified pixels are also performed on a pixel-by-pixel basis. Both the Xerox and Hewlett-Packard techniques examine an image pixel of interest, compare it and neighboring pixels to comparison templates in a two-dimensional, symmetrical array (with the pixel of interest positioned at the center of the array) and then make modifications to the pixel of interest if a pattern match is found with one of the comparison templates.
Each pixel in the entire print (i.e., 8.4 million pixels in a 300 dpi, 81/2.times.11 inch print) is compared to a large number of matching templates (more than 100 templates in the Hewlett-Packard technique). The types of corrections which can be made include breaking the identified pixel or pixels into smaller sub-pixels to enable image edge corrections using sub-pixels (Xerox) or modulating the size of the pixel by pulse width modulation or by positional adjustment in the fast scan direction (Hewlett-Packard).
The Xerox and Hewlett-Packard techniques operate on the image after a bit-mapped representation of the image has been produced. They do not require the additional memory and cost associated with the multi-plane bit image of the IBM approach. To this extent, they improve on the IBM process.
Other prior art anti-aliasing techniques, such as those employed in CRT's, are specific to continuous tone imaging systems, such as CRT's in which the pixel intensity can be modulated in a continuous tone, analog fashion. Electrophotography does not readily lend itself to continuous tone printing.
The above prior art techniques take a "pixel-oriented" view of the raster artifact problem. They provide a basis for "correcting" individual pixels based upon empirically-derived pixel corrections to improve the appearance of images. They do not directly address the underlying issue associated with the perception of raster artifacts, i.e., image edge morphology.
Image edge morphology relates to the spatially modulated shape characteristics of the edges of image elements. The perceptual response to jaggies is a response to the morphological characteristics of the edge of an image element. Humans have a psychophysical response to images which have perceived spatial errors, i.e., dimensional errors or spatially periodic fluctuations. Contrary to the above prior art techniques, this invention provides a method to resolve these artifacts based on morphological characteristics of images in a more efficient manner than the "central pixel correction" approaches employed, for example, in the Xerox and Hewlett-Packard patents.
Another type of objectionable artifact of halftone images is graininess. Images produced by high contrast raster and matrix imaging systems often are not capable of rendering good continuous tone pictorial images. Techniques have been developed in the graphic arts to simulate continuous tone images by employing halftone printing techniques. Halftoning, utilizing both optical screening and digital scanning techniques, is well understood in the art and will not be described here in detail.
Halftoning techniques produce a representation of an image which is intended to simulate a continuous tone pictorial scene using a high contrast imaging process. Variations in scene darkness are simulated by varying the local area coverage of the ink (or toner) used to produce the image. By locally modulating the ink area coverage of an image, a simulation of optical density modulation can be produced. Halftoning accomplishes this by utilizing an array of halftone dots and locally modulating the size (and corresponding coverage area) of the dots, thereby simulating continuous tone density modulation. In raster and matrix imaging systems, these halftone dots are typically constructed from clusters or sub-arrays of pixels. This is depicted graphically in FIG. 17.
The halftone dots in halftone imaging systems are typically arranged in a two-dimensional array of halftone dots with a uniform spacing between them. Ideally, the halftone array would consist of very closely spaced, small dots having a high spatial frequency dot pattern to minimize the perception of graininess in the halftone image. The spatial placement frequency of halftones is referred to as the halftone screen frequency. Experience in the graphic arts has shown that screen frequencies above 150 dots/inch produce very little detectable graininess, whereas screen frequencies between 10 and 85 dots/inch produce very noticeable and objectionable graininess.
In raster and matrix printing systems, halftone dots are constructed using arrays of imaged pixels. Since multiples of imaged pixels are required to construct halftone dots, halftone screen frequencies by necessity occur at lower spatial frequencies than printer addressability frequency. For example, if 26 density steps (white plus 25 levels of "gray") are desired from a 300 dpi laser printer, a halftone cell of 5.times.5 pixels would be required, resulting in a screen frequency of 300/5 or 60 dots/inch. The halftone images produced by such a system would have a very noticeable graininess.
The production of halftone images from a high-contrast raster or matrix imaging system requires a trade-off of two image output variables: screen graininess and number of gray levels. The larger the number of desired gray levels, the more imaging pixels will be required in the halftone cell and therefore the grainier the resulting halftone image becomes.
The perception of graininess in a halftone image is determined, once again, by the spatial frequency response to the observer. As is the case with jaggies and other spatially modulated artifacts, the highest degree of sensitivity to halftone structure occurs at spatial frequencies of about 0.3-3 cycles/mm. This corresponds to halftone screen frequencies of about 8-75 dots/inch.
The pictorial images printed by raster or matrix printing systems are typically downloaded from a host computer or an input scanner as a screened halftone representation of the image. These images typically have been halftoned using very simple halftoning algorithms and typically are screened at halftone frequencies which produce a very objectionable graininess in the printed image, for example, at 60 dpi.